1 /*
2 * Copyright (c) 2000, 2004, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26
27 package javax.print.attribute;
28
29 import java.io.Serializable;
30 import java.util.Vector;
31
32 /**
33 * Class SetOfIntegerSyntax is an abstract base class providing the common
34 * implementation of all attributes whose value is a set of nonnegative
35 * integers. This includes attributes whose value is a single range of integers
36 * and attributes whose value is a set of ranges of integers.
37 * <P>
38 * You can construct an instance of SetOfIntegerSyntax by giving it in "string
39 * form." The string consists of zero or more comma-separated integer groups.
40 * Each integer group consists of either one integer, two integers separated by
41 * a hyphen (<CODE>-</CODE>), or two integers separated by a colon
42 * (<CODE>:</CODE>). Each integer consists of one or more decimal digits
43 * (<CODE>0</CODE> through <CODE>9</CODE>). Whitespace characters cannot
44 * appear within an integer but are otherwise ignored. For example:
45 * <CODE>""</CODE>, <CODE>"1"</CODE>, <CODE>"5-10"</CODE>, <CODE>"1:2,
46 * 4"</CODE>.
47 * <P>
48 * You can also construct an instance of SetOfIntegerSyntax by giving it in
49 * "array form." Array form consists of an array of zero or more integer groups
50 * where each integer group is a length-1 or length-2 array of
51 * <CODE>int</CODE>s; for example, <CODE>int[0][]</CODE>,
52 * <CODE>int[][]{{1}}</CODE>, <CODE>int[][]{{5,10}}</CODE>,
53 * <CODE>int[][]{{1,2},{4}}</CODE>.
54 * <P>
55 * In both string form and array form, each successive integer group gives a
56 * range of integers to be included in the set. The first integer in each group
57 * gives the lower bound of the range; the second integer in each group gives
58 * the upper bound of the range; if there is only one integer in the group, the
59 * upper bound is the same as the lower bound. If the upper bound is less than
60 * the lower bound, it denotes a null range (no values). If the upper bound is
61 * equal to the lower bound, it denotes a range consisting of a single value. If
62 * the upper bound is greater than the lower bound, it denotes a range
63 * consisting of more than one value. The ranges may appear in any order and are
64 * allowed to overlap. The union of all the ranges gives the set's contents.
65 * Once a SetOfIntegerSyntax instance is constructed, its value is immutable.
66 * <P>
67 * The SetOfIntegerSyntax object's value is actually stored in "<I>canonical</I>
68 * array form." This is the same as array form, except there are no null ranges;
69 * the members of the set are represented in as few ranges as possible (i.e.,
70 * overlapping ranges are coalesced); the ranges appear in ascending order; and
71 * each range is always represented as a length-two array of <CODE>int</CODE>s
72 * in the form {lower bound, upper bound}. An empty set is represented as a
73 * zero-length array.
74 * <P>
75 * Class SetOfIntegerSyntax has operations to return the set's members in
76 * canonical array form, to test whether a given integer is a member of the
77 * set, and to iterate through the members of the set.
78 * <P>
79 *
80 * @author David Mendenhall
81 * @author Alan Kaminsky
82 */
83 public abstract class SetOfIntegerSyntax implements Serializable, Cloneable {
84
85 private static final long serialVersionUID = 3666874174847632203L;
86
87 /**
88 * This set's members in canonical array form.
89 * @serial
90 */
91 private int[][] members;
92
93
94 /**
95 * Construct a new set-of-integer attribute with the given members in
96 * string form.
97 *
98 * @param members Set members in string form. If null, an empty set is
99 * constructed.
100 *
101 * @exception IllegalArgumentException
102 * (Unchecked exception) Thrown if <CODE>members</CODE> does not
103 * obey the proper syntax.
104 */
105 protected SetOfIntegerSyntax(String members) {
106 this.members = parse (members);
107 }
108
109 /**
110 * Parse the given string, returning canonical array form.
111 */
112 private static int[][] parse(String members) {
113 // Create vector to hold int[] elements, each element being one range
114 // parsed out of members.
115 Vector theRanges = new Vector();
116
117 // Run state machine over members.
118 int n = (members == null ? 0 : members.length());
119 int i = 0;
120 int state = 0;
121 int lb = 0;
122 int ub = 0;
123 char c;
124 int digit;
125 while (i < n) {
126 c = members.charAt(i ++);
127 switch (state) {
128
129 case 0: // Before first integer in first group
130 if (Character.isWhitespace(c)) {
131 state = 0;
132 }
133 else if ((digit = Character.digit(c, 10)) != -1) {
134 lb = digit;
135 state = 1;
136 } else {
137 throw new IllegalArgumentException();
138 }
139 break;
140
141 case 1: // In first integer in a group
142 if (Character.isWhitespace(c)){
143 state = 2;
144 } else if ((digit = Character.digit(c, 10)) != -1) {
145 lb = 10 * lb + digit;
146 state = 1;
147 } else if (c == '-' || c == ':') {
148 state = 3;
149 } else if (c == ',') {
150 accumulate (theRanges, lb, lb);
151 state = 6;
152 } else {
153 throw new IllegalArgumentException();
154 }
155 break;
156
157 case 2: // After first integer in a group
158 if (Character.isWhitespace(c)) {
159 state = 2;
160 }
161 else if (c == '-' || c == ':') {
162 state = 3;
163 }
164 else if (c == ',') {
165 accumulate(theRanges, lb, lb);
166 state = 6;
167 } else {
168 throw new IllegalArgumentException();
169 }
170 break;
171
172 case 3: // Before second integer in a group
173 if (Character.isWhitespace(c)) {
174 state = 3;
175 } else if ((digit = Character.digit(c, 10)) != -1) {
176 ub = digit;
177 state = 4;
178 } else {
179 throw new IllegalArgumentException();
180 }
181 break;
182
183 case 4: // In second integer in a group
184 if (Character.isWhitespace(c)) {
185 state = 5;
186 } else if ((digit = Character.digit(c, 10)) != -1) {
187 ub = 10 * ub + digit;
188 state = 4;
189 } else if (c == ',') {
190 accumulate(theRanges, lb, ub);
191 state = 6;
192 } else {
193 throw new IllegalArgumentException();
194 }
195 break;
196
197 case 5: // After second integer in a group
198 if (Character.isWhitespace(c)) {
199 state = 5;
200 } else if (c == ',') {
201 accumulate(theRanges, lb, ub);
202 state = 6;
203 } else {
204 throw new IllegalArgumentException();
205 }
206 break;
207
208 case 6: // Before first integer in second or later group
209 if (Character.isWhitespace(c)) {
210 state = 6;
211 } else if ((digit = Character.digit(c, 10)) != -1) {
212 lb = digit;
213 state = 1;
214 } else {
215 throw new IllegalArgumentException();
216 }
217 break;
218 }
219 }
220
221 // Finish off the state machine.
222 switch (state) {
223 case 0: // Before first integer in first group
224 break;
225 case 1: // In first integer in a group
226 case 2: // After first integer in a group
227 accumulate(theRanges, lb, lb);
228 break;
229 case 4: // In second integer in a group
230 case 5: // After second integer in a group
231 accumulate(theRanges, lb, ub);
232 break;
233 case 3: // Before second integer in a group
234 case 6: // Before first integer in second or later group
235 throw new IllegalArgumentException();
236 }
237
238 // Return canonical array form.
239 return canonicalArrayForm (theRanges);
240 }
241
242 /**
243 * Accumulate the given range (lb .. ub) into the canonical array form
244 * into the given vector of int[] objects.
245 */
246 private static void accumulate(Vector ranges, int lb,int ub) {
247 // Make sure range is non-null.
248 if (lb <= ub) {
249 // Stick range at the back of the vector.
250 ranges.add(new int[] {lb, ub});
251
252 // Work towards the front of the vector to integrate the new range
253 // with the existing ranges.
254 for (int j = ranges.size()-2; j >= 0; -- j) {
255 // Get lower and upper bounds of the two ranges being compared.
256 int[] rangea = (int[]) ranges.elementAt (j);
257 int lba = rangea[0];
258 int uba = rangea[1];
259 int[] rangeb = (int[]) ranges.elementAt (j+1);
260 int lbb = rangeb[0];
261 int ubb = rangeb[1];
262
263 /* If the two ranges overlap or are adjacent, coalesce them.
264 * The two ranges overlap if the larger lower bound is less
265 * than or equal to the smaller upper bound. The two ranges
266 * are adjacent if the larger lower bound is one greater
267 * than the smaller upper bound.
268 */
269 if (Math.max(lba, lbb) - Math.min(uba, ubb) <= 1) {
270 // The coalesced range is from the smaller lower bound to
271 // the larger upper bound.
272 ranges.setElementAt(new int[]
273 {Math.min(lba, lbb),
274 Math.max(uba, ubb)}, j);
275 ranges.remove (j+1);
276 } else if (lba > lbb) {
277
278 /* If the two ranges don't overlap and aren't adjacent but
279 * are out of order, swap them.
280 */
281 ranges.setElementAt (rangeb, j);
282 ranges.setElementAt (rangea, j+1);
283 } else {
284 /* If the two ranges don't overlap and aren't adjacent and
285 * aren't out of order, we're done early.
286 */
287 break;
288 }
289 }
290 }
291 }
292
293 /**
294 * Convert the given vector of int[] objects to canonical array form.
295 */
296 private static int[][] canonicalArrayForm(Vector ranges) {
297 return (int[][]) ranges.toArray (new int[ranges.size()][]);
298 }
299
300 /**
301 * Construct a new set-of-integer attribute with the given members in
302 * array form.
303 *
304 * @param members Set members in array form. If null, an empty set is
305 * constructed.
306 *
307 * @exception NullPointerException
308 * (Unchecked exception) Thrown if any element of
309 * <CODE>members</CODE> is null.
310 * @exception IllegalArgumentException
311 * (Unchecked exception) Thrown if any element of
312 * <CODE>members</CODE> is not a length-one or length-two array or if
313 * any non-null range in <CODE>members</CODE> has a lower bound less
314 * than zero.
315 */
316 protected SetOfIntegerSyntax(int[][] members) {
317 this.members = parse (members);
318 }
319
320 /**
321 * Parse the given array form, returning canonical array form.
322 */
323 private static int[][] parse(int[][] members) {
324 // Create vector to hold int[] elements, each element being one range
325 // parsed out of members.
326 Vector ranges = new Vector();
327
328 // Process all integer groups in members.
329 int n = (members == null ? 0 : members.length);
330 for (int i = 0; i < n; ++ i) {
331 // Get lower and upper bounds of the range.
332 int lb, ub;
333 if (members[i].length == 1) {
334 lb = ub = members[i][0];
335 } else if (members[i].length == 2) {
336 lb = members[i][0];
337 ub = members[i][1];
338 } else {
339 throw new IllegalArgumentException();
340 }
341
342 // Verify valid bounds.
343 if (lb <= ub && lb < 0) {
344 throw new IllegalArgumentException();
345 }
346
347 // Accumulate the range.
348 accumulate(ranges, lb, ub);
349 }
350
351 // Return canonical array form.
352 return canonicalArrayForm (ranges);
353 }
354
355 /**
356 * Construct a new set-of-integer attribute containing a single integer.
357 *
358 * @param member Set member.
359 *
360 * @exception IllegalArgumentException
361 * (Unchecked exception) Thrown if <CODE>member</CODE> is less than
362 * zero.
363 */
364 protected SetOfIntegerSyntax(int member) {
365 if (member < 0) {
366 throw new IllegalArgumentException();
367 }
368 members = new int[][] {{member, member}};
369 }
370
371 /**
372 * Construct a new set-of-integer attribute containing a single range of
373 * integers. If the lower bound is greater than the upper bound (a null
374 * range), an empty set is constructed.
375 *
376 * @param lowerBound Lower bound of the range.
377 * @param upperBound Upper bound of the range.
378 *
379 * @exception IllegalArgumentException
380 * (Unchecked exception) Thrown if the range is non-null and
381 * <CODE>lowerBound</CODE> is less than zero.
382 */
383 protected SetOfIntegerSyntax(int lowerBound, int upperBound) {
384 if (lowerBound <= upperBound && lowerBound < 0) {
385 throw new IllegalArgumentException();
386 }
387 members = lowerBound <=upperBound ?
388 new int[][] {{lowerBound, upperBound}} :
389 new int[0][];
390 }
391
392
393 /**
394 * Obtain this set-of-integer attribute's members in canonical array form.
395 * The returned array is "safe;" the client may alter it without affecting
396 * this set-of-integer attribute.
397 *
398 * @return This set-of-integer attribute's members in canonical array form.
399 */
400 public int[][] getMembers() {
401 int n = members.length;
402 int[][] result = new int[n][];
403 for (int i = 0; i < n; ++ i) {
404 result[i] = new int[] {members[i][0], members[i][1]};
405 }
406 return result;
407 }
408
409 /**
410 * Determine if this set-of-integer attribute contains the given value.
411 *
412 * @param x Integer value.
413 *
414 * @return True if this set-of-integer attribute contains the value
415 * <CODE>x</CODE>, false otherwise.
416 */
417 public boolean contains(int x) {
418 // Do a linear search to find the range that contains x, if any.
419 int n = members.length;
420 for (int i = 0; i < n; ++ i) {
421 if (x < members[i][0]) {
422 return false;
423 } else if (x <= members[i][1]) {
424 return true;
425 }
426 }
427 return false;
428 }
429
430 /**
431 * Determine if this set-of-integer attribute contains the given integer
432 * attribute's value.
433 *
434 * @param attribute Integer attribute.
435 *
436 * @return True if this set-of-integer attribute contains
437 * <CODE>theAttribute</CODE>'s value, false otherwise.
438 */
439 public boolean contains(IntegerSyntax attribute) {
440 return contains (attribute.getValue());
441 }
442
443 /**
444 * Determine the smallest integer in this set-of-integer attribute that is
445 * greater than the given value. If there are no integers in this
446 * set-of-integer attribute greater than the given value, <CODE>-1</CODE> is
447 * returned. (Since a set-of-integer attribute can only contain nonnegative
448 * values, <CODE>-1</CODE> will never appear in the set.) You can use the
449 * <CODE>next()</CODE> method to iterate through the integer values in a
450 * set-of-integer attribute in ascending order, like this:
451 * <PRE>
452 * SetOfIntegerSyntax attribute = . . .;
453 * int i = -1;
454 * while ((i = attribute.next (i)) != -1)
455 * {
456 * foo (i);
457 * }
458 * </PRE>
459 *
460 * @param x Integer value.
461 *
462 * @return The smallest integer in this set-of-integer attribute that is
463 * greater than <CODE>x</CODE>, or <CODE>-1</CODE> if no integer in
464 * this set-of-integer attribute is greater than <CODE>x</CODE>.
465 */
466 public int next(int x) {
467 // Do a linear search to find the range that contains x, if any.
468 int n = members.length;
469 for (int i = 0; i < n; ++ i) {
470 if (x < members[i][0]) {
471 return members[i][0];
472 } else if (x < members[i][1]) {
473 return x + 1;
474 }
475 }
476 return -1;
477 }
478
479 /**
480 * Returns whether this set-of-integer attribute is equivalent to the passed
481 * in object. To be equivalent, all of the following conditions must be
482 * true:
483 * <OL TYPE=1>
484 * <LI>
485 * <CODE>object</CODE> is not null.
486 * <LI>
487 * <CODE>object</CODE> is an instance of class SetOfIntegerSyntax.
488 * <LI>
489 * This set-of-integer attribute's members and <CODE>object</CODE>'s
490 * members are the same.
491 * </OL>
492 *
493 * @param object Object to compare to.
494 *
495 * @return True if <CODE>object</CODE> is equivalent to this
496 * set-of-integer attribute, false otherwise.
497 */
498 public boolean equals(Object object) {
499 if (object != null && object instanceof SetOfIntegerSyntax) {
500 int[][] myMembers = this.members;
501 int[][] otherMembers = ((SetOfIntegerSyntax) object).members;
502 int m = myMembers.length;
503 int n = otherMembers.length;
504 if (m == n) {
505 for (int i = 0; i < m; ++ i) {
506 if (myMembers[i][0] != otherMembers[i][0] ||
507 myMembers[i][1] != otherMembers[i][1]) {
508 return false;
509 }
510 }
511 return true;
512 } else {
513 return false;
514 }
515 } else {
516 return false;
517 }
518 }
519
520 /**
521 * Returns a hash code value for this set-of-integer attribute. The hash
522 * code is the sum of the lower and upper bounds of the ranges in the
523 * canonical array form, or 0 for an empty set.
524 */
525 public int hashCode() {
526 int result = 0;
527 int n = members.length;
528 for (int i = 0; i < n; ++ i) {
529 result += members[i][0] + members[i][1];
530 }
531 return result;
532 }
533
534 /**
535 * Returns a string value corresponding to this set-of-integer attribute.
536 * The string value is a zero-length string if this set is empty. Otherwise,
537 * the string value is a comma-separated list of the ranges in the canonical
538 * array form, where each range is represented as <CODE>"<I>i</I>"</CODE> if
539 * the lower bound equals the upper bound or
540 * <CODE>"<I>i</I>-<I>j</I>"</CODE> otherwise.
541 */
542 public String toString() {
543 StringBuffer result = new StringBuffer();
544 int n = members.length;
545 for (int i = 0; i < n; i++) {
546 if (i > 0) {
547 result.append (',');
548 }
549 result.append (members[i][0]);
550 if (members[i][0] != members[i][1]) {
551 result.append ('-');
552 result.append (members[i][1]);
553 }
554 }
555 return result.toString();
556 }
557
558 }